وزارت علوم، تحقیقات و فناوری

دانشگاه علوم و فنون مازندران

پایان نامه

مقطع کارشناسی ارشد

رشته :مهندسی فناوری اطلاعات

عنوان/موضوع: پیش بینی لینک در شبکه های اجتماعی با استفاده از شبکه بیزین

استاد راهنما : دکتر علی رضا پورابراهیمی

استاد مشاور : دکتر بابک شیرازی

بهار1393

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی شود

(در فایل دانلودی نام نویسنده موجود است)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن است هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود ولی در فایل دانلودی همه چیز مرتب و کامل است)

چکیده

شبکه های اجتماعی شبکه هایی دینامیک هستند که مدام در حال افزایش اعضا و ارتباطات و لینکهای بین آنها هستند و متاسفانه این لینکها ممکن است به خاطر فرآیند ایجاد ناقص و یا به خاطر این که این هنوز در این شبکه ها انعکاس نیافته اند، از دست برود. در رابطه با این لینکها و ارتباطات مساله پیش بینی لینک که یک امر مهم برای تحلیل شبکه های اجتماعی است، اهمیت پیدا می کند. این مساله به معنی پیش بینی احتمال برقراری یک ارتباط بین دو رأس است ، با دانستن این مساله که در حال حاضر ارتباطی بین این دو رأس وجود ندارد .

سه رویکرد برای انجام پیش بینی لینک وجود دارد: اولین رویکرد مدل های سنتی )غیربیزین( است که مجموعه ای از ویژگی ها را برای آموزش یک مدل دسته بندی باینری استخراج می کند. دومی رویکردهای احتمالاتی است که احتمال الحاق موجودیت ها در یک شبکه اجتماعی را با استفاده از مدل های گرافیکی بیزین مدل می کندو سومین رویکرد ،رویکردهای جبرخطی-آماری است..ایده اصلی در استفاده از مفاهیم بیزین، بدست آوردن یک احتمال ثانویه است که به شانس اتصال یک جفت رأس که مورد نظر ماست اشاره دارد.در این گزارش با استفاده از دسته بندی کننده ساده بیزین به پیش بینی لینک میپردازیم.

یادگیری بیزین یکی ازموثرترین الگوریتم های یادگیری برای داده کاوی داده ها با استفاده از یادگیری ماشین میباشد. شبکه بیزین به تنهایی یک دسته بندی ساده براساس تئوری بیزین میباشد از این رو برای بهبود پیش بینی دسته بندی بیزی میتوان چهار راهکار ارایه داد: استخراج ویژگی ، گسترش ساختاری ،یادگیری محلی و گسترش داده ها. در این گزارش با استفاده از استخراج ویژگیها که یکی از مراحل پیش پردازش داده ها میباشد به بهبود دسته بندی ها میپردازیم.الگوریتم های متاهیورستیک مبتنی بر جمعیت ازقبیل الگوریتم رقابت استعماری، الگوریتم بهینه سازی ازدحام ذرات، شبکه عصبی و الگوریتم ژنتیک  در جستجوی زیرمجموعه ویژگی ها کارایی بالایی را در استخراج ویژگی مسایل بزرگ و پیچیده از جمله شبکه های پیچیده دارند، در این گزارش برای بهبود پیش بینی ها در شبکه ی اجتماعی فلیکر  استفاده میکنیم .

   کلمات کلیدی : شبکه های اجتماعی ، پیش بینی لینک ، شبکه های بیزین ، استخراج ویژگی و الگوریتم های متاهیورستیک مبتنی بر جمعیت

فهرست مطالب

فصل اول 1

مقدمه و کلیات تحقیق 1

1-1-مقدمه 2

1-2-کلیات و مسایل تحقیق 5

1-2-1-تشریح و بیان موضوع تحقیق 5

1-2-2-ضرورت انجام تحقیق 6

1-2-3-فرضیه ها و اهداف تحقیق 8

1-2-4-روش انجام تحقیق 9

1-3-تاریخچه شبکه های اجتماعی 10

1-4-تعریف شبکه اجتماعی 11

1-5-انواع شبکه های اجتماعی 14

1-5-1-بر مبنای نوع ارتباطات 14

1-5-2-ارتباطات اجتماعی 14

1-5-3-شبکه بندی 14

1-5-4-ناوبری 15

1-5-5-بر مبنای نوع فعالیت 15

1-5-6-شبکه های اجتماعی اطلاعاتی 16

1-5-7-شبکه های اجتماعی تخصصی 17

1-5-8 -شبکه های اجتماعی آموزشی 17

1-5-9-شبکه های اجتماعی سرگرمی 17

1-5-10-شبکه های اجتماعی علمی 17

1-5-11-شبکه های اجتماعی خبری 18

1-5-12-از نظر باز یا بسته از نظر اعضا 18

1-5-13-شبکه های با عضویت آزاد و باز برای افراد 18

1-5-14-شبکه های با عضویت محدود شده به داشتن شرایطی خاص توسط افراد 18

1-5-15-شبکه های بسته و عضویت تنها در صورت دعوت توسط سایر اعضا 19

1-5-16-بر مبنای سطح پوشش. 19

1-5-17-شبکه های جهانی 19

1-5-18-شبکه های منطقه ای 19

1-5-19-شبکه های ملی 20

1-5-20-شبکه های سازمانی 20

1-6-ویژگی های انحصاری شبکه های اجتماعی 20

1-7-اهداف و کارکردهای شبکه های اجتماعی 20

1-7-1-سازماندهی انواع گروه های اجتماعی مجازی 21

1-7-2-توسعه مشارکت های اجتماعی 21

1-7-3-به اشتراک گذاشتن علاقه مندی ها توسط اعضا 21

1-7-4-ایجاد محتوا توسط اعضا 22

1-7-5-تبلیغات هدفمند اینترنتی 22

1-8-مزایای شبکه های اجتماعی 22

1-8-1-انتشار سریع و آزادانه اخبار و اطلاعات، افزایش قدرت تحلیل و تقویت روحیه انتقادی 22

1-8-2-امکان عبور از مرزهای جغرافیایی و آشنایی با افراد، جوامع و فرهنگ های مختلف  23

1-8-3-شکل گیری و تقویت خرد جمعی 23

1-8-4- امکان بیان ایده ها به صورت آزادانه و آشنایی با ایده ها، افکار و سلیقه های دیگران 23

1-8-5-کارکرد تبلیغی و محتوایی 24

1-8-6-ارتباط مجازی مستمر با دوستان و آشنایان 24

1-8-7-تبلیغ و توسعه ارزش های انسانی و اخلاقی در عرصه جهانی 24

1-8-8-یکپارچه سازی بسیاری از امکانات اینترنتی و وبی 25

1-8-9-توسعه مشارکت های مفید اجتماعی 25

1-8-10-ا فزایش سرعت در فرایند آموزش و ایجاد ارتباط شبانه روزی بین استاد و شاگرد 25

1-8-11- افزایش اعتماد، صمیمیت و صداقت در فضای سایبر 26

1-9 -پیامدهای منفی شبکه های اجتماعی 26

1-9-1- شکل گیری و ترویج سریع شایعات و اخبار کذب 26

1-9-2-تبلیغات ضد دینی و القای شبهات 27

1-9-3- نقض حریم خصوصی افراد 27

1-9-4- انزوا و دور ماندن از محیط های واقعی اجتماع 27

1-9-5- تأثیرات منفیِ رفتاری 28

1-10- شبکه های اجتماعی در ایران 28

جمع بندی 31

فصل دوم 33

تحلیل شبکه های اجتماعی 33

2-1-مقدمه 34

2-2- داده های موجود در شبکه های اجتماعی 35

2-3 -روابط، اساس شبکه های اجتماعی 38

2–4 اهداف تحلیل شبکه های اجتماعی 39

2–5 حوزه های مختلف فعالیت در تحلیل شبکه های اجتماعی 39

جمع بندی 42

فصل سوم 43

پیش بینی لینک در شبکه های اجتماعی 43

3–1 مقدمه 44

3-2 -سابقه تحقیقات و مطالعات انجام گرفته 46

3-3-روش های یادگیری ماشین برای پیش بینی لینک. 48

3-3- -1یادگیری بدون ناظر برای پیش بینی لینک. 49

3-3-2-یادگیری با ناظر برای پیش بینی لینک. 50

3-4- رویکردهای موجود در پیش بینی لینک. 51

3-3-1- رویکرد مبتنی بر شباهت 53

3-3-1–1استخراج ویژگی 55

3-3-2- رویکرد مبتنی بر مدل های احتمالاتی 59

3-3-2-1-ویژگیهای یادگیری بیزین 62

3-3-3 -روش های جبر خطی 63

جمع بندی 65

فصل چهارم 68

پیش بینی لینک در شبکه های اجتماعی با استفاده از شبکه های بیزین 68

4-1-مقدمه 69

4-2-مجموعه داده های مورد استفاده 69

4-3-معیارهای ارزیابی 71

4-4-شاخص های مورد استفاده در پیش بینی لینک. 75

4-5-پیش بینی لینک با استفاده از شبکه بیزین 76

4-6-بهبود دسته یندی در شبکه های بیزین: 81

4-6-1-الگوریتم رقابت استعماری: 83

4-6-2-الگوریتم ژنتیک: 86

4-6-3-الگوریتم بهینه سازی ازدحام ذرات 90

4-6-4-الگوریتم شبکه عصبی مصنوعی 91

4-7-نتایج تجربی حاصل از پیاده سازی الگوریتم ها 93

4-7-1-نمودار های حاصل از اجرای الگوریتم های مبتنی بر جمعیت 95

نتیجه گیری 100

فصل پنجم 101

نتیجه گیری و پیشنهادات. 101

5-1-خلاصه مطالب. 102

5-2- پیشنهادات آینده 102

5-3-مشکلات موجود در روش های پیشگویی پیوند 104

5-4-مشکلات عملی در یادگیری بیزین و دسته بندی کننده ی بیزین 105

مقاله مستخرج از پایان نامه 106

مقاله انگلیسی برای ژورنال: 106

منابع: 107

فهرست جداول

جدول 1-1 شبکه های اجتماعی در ایران 30

جدول 3-1 ویژگیهای ساختاری مربوط به جفت راس های گراف شبکه های اجتماعی 56

جدول 4-1 ویژگی های داده های جمع آوری شده فلیکر 70

جدول 4-2 ماتریس در همریختگی:شامل معیارهایی برای محاسبه نتایج پیش بینی ها 72

جدول 4-3 شاخص های دسته بندی کننده 76

جدول 4-3 Confusion matrix 80

جدول 4-3 نتایج پیش بینی لینک با استفاده از شبکه های بیزین 81

جدول4-4  مقایسه الگوریتم های بهینه سازی تکاملی در بهبود پیش بینی لینک. 95

فهرست تصاویر و نمودار

شکل 2-1 نمونه کوچکی از گراف یک شبکه اجتماعی 36

شکل 3-1 ارتباطات بین افراد شامل گره و یال های متصل و غیر متصل در شبکه اجتماعی 44

شکل 3-2 نمایی از پیش بینی لینک در زمان T+1 45

شکل 3-3 رویکرد های موجود در پیش بینی لینک. 53

شکل 4-1  توزیع جمعیت در شبکه اجتماعی فلیکر 69

شکل 4-2  مثالی در مورد محاسبه مقدارPrecision و AUC 74

شکل 4- 3 منحنی ROCبرای مقایسه سه شاخص همسایگان مشترک,کاتز و آدامیک آدار 76

شکل 4-2  نمایی از یک مدل بیزی ساده که به عنوان یک شبکه بیزین عمل مینماید 78

 شکل 4-3  گراف و roc curve precision-recall 81

شکل4-6  فلوچارت الگوریتم رقابت استعماری 86

شکل 4-7  شمای کلی شبه کد الگوریتم ژنتیک. 89

شکل4- 8نمایی از الگوریتم بهینه سازی ازدحام ذرات. 91

نمودار4-5   precision- recall 95

نمودار 4-6مساحت زیر نمودار ROC curve 96

نمودار 4-7 نمودار تکرار ها وکارایی الگوریتم ها(Iteration-Best cost) 97

شکل5-1 فعالیت کاربران در شبکه اجتماعی فیس بوک. 102

شکل 5-1  نسبت مثال های مثبت و منفی در شبکه های اجتماعی 103

مقدمه

اینترنت به عنوان یکی از مهم ترین ابداعات بشر در قرن اخیر، با قابلیت ها و کارکردهای متعدد و گسترده اش، بخش های مختلف زندگی انسانی را تحت تأثیرات مثبت و منفی خود قرار داده است. مبنا و هدف اصلی اینترنت، برداشتن فاصله جغرافیایی میان انسان های سراسر دنیا و ایجاد تحول در عرصه ارتباطات و تبادل اطلاعات است.[1]

اینترنت، کار خود را به عنوان ابزار ارتباط متخصصان و خصوصاً جهت تبادل داده ها و منابع تحقیقاتی، شروع کرد و به مرور زمان توانست خود را تا سطح برقراری ارتباط بین افراد معمولی از طریق پست الکترونیکی ارتقا بخشد. پس از مدتی، اینترنت به منزله فضایی جدید جهت بسط فعالیت های تجاری در امور نقل و انتقالات مالی، بازاریابی و همچنین ابزار پیگیری برای مصرف کنندگان، مورد توجه واقع شد. وبلاگ ها و وب سایت ها، نرم افزارهای گفتگوی برخط، سرویس های پست الکترونیک و غیره امکانات جدیدی بودند که در پرتوی اینترنت و شبکه جهانی وب، در اختیار کاربران قرار گرفتند.

برای دانلود متن کامل پایان نامه اینجا کلیک کنید

لینک بالا اشتباه است

برای دانلود متن کامل اینجا کلیک کنید

       

:: بازدید از این مطلب : 1007